#!/usr/bin/env python

def shell_sort(nums):
    def insert_sort(nums, start, gap):
        for i in range(start + gap, len(nums), gap):
            pos = i
            tmp = nums[i]
            while pos >= gap and nums[pos - gap] > tmp:
                nums[pos] = nums[pos - gap]
                pos -= gap
            
            nums[pos] = tmp
    
    gap = len(nums) // 2
    while gap > 0:
        for i in range(gap):
            insert_sort(nums, i, gap)
    
        gap //= 2

    return nums


if __name__ == "__main__":
    import random
    nums = [random.randint(0, 100) for _ in range(20)]

    print(nums)
    print(shell_sort(nums)) 